package com.mccken.practice.data_structure.data_03;

import com.mccken.practice.algorithm.common.TreeNode_Common;

/**
 * 最小公共祖先节点
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 23:34
 **/
public class Lca {

	/**
	 * 二叉树递归三思
	 *  递归后的整体来选择
	 * 
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	public TreeNode_Common lowestCommonAncestor(TreeNode_Common root, TreeNode_Common p, TreeNode_Common q){
		// base case
		if (root == null) {
			return null;
		}
		
		if (p == root || q == root) {
			return root;
		}
		
		TreeNode_Common left = lowestCommonAncestor(root.left, p, q);
		TreeNode_Common right = lowestCommonAncestor(root.right, p, q);
		
		// 情况1
		if (left != null && right != null) {
			return root;
		}
		
		
		// 情况2
		if (left == null && right == null){
			return root;
		}
		
		// 情况3
		return left == null ? right : left;
	}
}
